package com.cty._02_HighQualityCode._26_SubstructureInTree;

/**
 * @Auther: cty
 * @Date: 2020/7/9 15:20
 * @Description: 面试题26：树的子结构
 * 题目：输入两棵二叉树A和B，判断B是不是A的子结构。
 * @version: 1.0
 */
public class SubstructureInTree {

    private static boolean equal(double value1, double value2){
        if((value1-value2>-0.0000001) && (value1-value2<0.0000001))
            return true;
        else
            return false;
    }

    private static boolean dosTree1HasTree2(BinaryTreeNode treeRoot1, BinaryTreeNode treeRoot2){
        if(treeRoot2 == null)
            return true;
        if(treeRoot1 == null)
            return false;
        if(!equal(treeRoot1.value, treeRoot2.value))
            return false;

        return dosTree1HasTree2(treeRoot1.leftChild, treeRoot2.leftChild) && dosTree1HasTree2(treeRoot1.rightChild, treeRoot2.rightChild);
    }

    public static boolean hasSubtree(BinaryTreeNode treeRoot1, BinaryTreeNode treeRoot2){
        boolean result = false;

        if(treeRoot1!=null && treeRoot2!=null){
            if(equal(treeRoot1.value, treeRoot2.value))
                result = dosTree1HasTree2(treeRoot1, treeRoot2);
            if(!result)
                result = hasSubtree(treeRoot1.leftChild, treeRoot2);
            if(!result)
                result = hasSubtree(treeRoot1.rightChild, treeRoot2);
        }
        return result;
    }  // end hasSubtree()

}  // end class

class BinaryTreeNode {

    double value;
    BinaryTreeNode leftChild;
    BinaryTreeNode rightChild;

    public BinaryTreeNode(){}
    public BinaryTreeNode(double value){
        this.value = value;
    }

}  // end class
